package algorithm;

import java.util.Arrays;

public class Algorithm {

    private static final int[] sortedNums = {1, 2, 3, 4, 5, 6, 7, 8};

    public static void main(String[] args) {
        //System.out.println(binary(sortedNums, 6));
        //bubble();
        //choose();
        //insert();
        shell();
    }

    private static int[] nums = {3, 5, 9, 1, 4, 2, 7, 6};

    /** 排序 */
    //希尔排序
    private static void shell() {
        for (int step = nums.length / 2; step > 0; step /= 2) {
            for (int i = step; i < nums.length; i++) {
                int value = nums[i];
                int j;
                for (j = i - step; j >= 0 && value < nums[j]; j -= step) {
                    nums[j + step] = nums[j];
                }
                nums[j + step] = value;
            }
            System.out.println("第step=" + step + "次:" + Arrays.toString(nums));
        }
        System.out.println("希尔排序:" + Arrays.toString(nums));
    }

    //插入排序
    private static void insert() {
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j;
            for (j = i - 1; j >= 0 && temp < nums[j]; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
            System.out.println("第i=" + i + "次:" + Arrays.toString(nums));
        }
        System.out.println("插入排序:" + Arrays.toString(nums));
    }


    //选择排序
    private static void choose() {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i; j < nums.length; j++) {
                if (nums[minIndex] > nums[j]) {
                    minIndex = j;
                }
            }
            int temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;
            System.out.println("第i=" + i + "次:" + Arrays.toString(nums));
        }
        System.out.println("选择排序后:" + Arrays.toString(nums));
    }

    //冒泡排序
    public static void bubble() {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
                System.out.println("第j=" + j + "次:" + Arrays.toString(nums));
            }
            System.out.println("第i=" + i + "次:" + Arrays.toString(nums));
        }
        System.out.println(Arrays.toString(nums));
    }

    /** 查找 */
    //二分(折半)查找
    //要求有序和顺序存储
    private static int binary(int[] nums, int key) {
        int low = 0;
        int high = nums.length - 1;
        int middle = 0;

        while (low <= high) {
            middle = (low + high) / 2;

            if (nums[middle] == key) {
                return middle;
            } else if (nums[middle] < key) {
                low = middle + 1;
            } else if (nums[middle] > key) {
                high = middle - 1;
            }
        }

        return -1;
    }


}
